Geospatial information systems (GIS) can generate realistic three-dimensional models of a variety of geographical environments and terrains. These systems can be utilized by system users to access the models and conveniently obtain information concerning particular geographic locations that are of interest to the users. Some conventional geospatial information systems provide users access to models of urban environments whose features have been digitized from aerial images of the environments.
Algorithms for automatically generating realistic three-dimensional models of urban environments have been the subject of research for many years. Historically such models have been used for urban planning purposes or for virtual tourist guides. Since the advent of interactive geospatial system applications the demand for fully automated systems has increased as the costs related to manual processing of large amounts of data that are involved in generating the models are excessive.
A conventional approach to generating realistic three-dimensional models of urban environments includes the use of feature based modeling algorithms which show good results for suburban areas. A drawback of such approaches is their reliance on sparse line features to describe the complete geometry of a building. It has been discovered that existing additional data (cadastral maps and GIS data for example) can help in the reconstruction task. However, external data sources require careful registration and limit the applicability of the algorithms to cities where such information is readily available. Additionally, such a dependency increases costs at large scale deployment.
A different group of algorithms concentrate on the analysis of dense altimetry data obtained from laser scans or dense stereo matching. The extraction of buildings in those point clouds is either performed based on a ground plan or the segmentation of the point clouds into local maxima. Such segmentation approaches which can be based solely on height information, however, are prone to failure if buildings are surrounded by trees and require a constrained model to overcome the smoothness of the data at height discontinuities (where the data should actually reflect discontinuity). Some conventional approaches combine elevation data from a LIDAR (laser radar) scan with satellite imagery using rectilinear line cues. This approach is, however, limited to determining the outline of a building.
In general conventional reconstruction algorithms need either an additional ground plan or restrictive constraints that limit the scope of the method to specific families of buildings (only perpendicular corners or parallel eave lines for example). They also consider only planar approximations which yield poor results for domes and spires. Accordingly, their effectiveness in modeling real world urban environments is limited because their effectiveness in modeling ubiquitous features of such environments such as trees, domes and spires is limited.